/**
 * 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
 * https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
 */
const { createTreeNode } = require('../../libs/public');

/**
 * @param {TreeNode} root
 * @param {TreeNode} target
 * @return {TreeNode[]}
 */
function getAnsLine(root, target) {
  if (!root) {
    return null;
  }
  if (root === target) {
    return [root];
  }
  const leftRes = getAnsLine(root.left, target);
  if (leftRes) {
    leftRes.unshift(root);
    return leftRes;
  }
  const rightRes = getAnsLine(root.right, target);
  if (rightRes) {
    rightRes.unshift(root);
    return rightRes;
  }
  return null;
}

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
function lowestCommonAncestor(root, p, q) {
  const pAnsLine = getAnsLine(root, p);
  const qAnsLine = getAnsLine(root, q);
  let index = 0;
  while (pAnsLine[index + 1] === qAnsLine[index + 1]) {
    index += 1;
  }
  return pAnsLine[index];
}

let root;

root = createTreeNode([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);
console.log(lowestCommonAncestor(root, root.left, root.right) === root);
root = createTreeNode([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);
console.log(lowestCommonAncestor(root, root.left, root.left.right) === root.left);
